【题解】 「网络流24题」餐巾计划问题 网络流 luoguP1251 | Qiuly's blog!

【题解】 「网络流24题」餐巾计划问题 网络流 luoguP1251

Posted on | Edited on | In | Comments:

实际上这道题可以用贪心解的……但是码量惊人 $QwQ$ 。

于是上网络流吧……这题显然是费用流。

对于每一天，我们将其拆成两个点，一个表示这天的早晨，一个表示这天的晚上。

我们从源点向每一天的晚上连一条边权为 $x$ 费用为 $0​$ 的边，表示这一天我们需要处理的餐巾数，就是白天用掉的餐巾。

每一天的早晨，这些餐巾来自题目给出的地方，并且最终连向汇点，边权为 $x$ 费用为 $0$ 。

然后考虑每天早上餐巾的来源，现在题目给了四个操作：

  • 买新的
  • 丢到快洗店
  • 丢到慢洗店
  • 弃疗

对于买新的，我们只需要从源点连一条边权为 $inf$ 费用为 $p$ 的边到这一天的白天，我们餐巾的获取都来自源点。

丢到快洗店，也就是说第 $i$ 天晚上这些没有处理的毛巾丢到快洗店，那么第 $i+m$ 天将洗完，这个时候可以在早晨收到餐巾，于是从 $i$ 的晚上连一条边权为 $inf$ 费用为 $f$ 的边连向 $i+m$ 的白天。

丢到慢洗店，这个跟快洗店是一个道理。

关于弃疗，就是说放着不管了，可以理解为第 $i$ 天晚上的餐巾留到了第 $i+1$ 天，并且这些餐巾是不能用的，那么不会连向 $i+1$ 的早晨，于是从 $i$ 的晚上连一条边权为 $inf$ 费用为 $f$ 的边连向 $i+1$ 的晚上。

然后跑一边费用流板子就好了，注意要开 $long long$ 。

至于上面四个选项为什么边的容量都设为 $inf$ ，我们就拿买新的来说吧，题目又没有限制你最多买多少，所以就是允许你可以一直买，买无限条，就当成 $inf$ 啦。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<cmath>
#include<queue>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>

#define ll long long
#define id(type,x) ((type)*n+x)
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y)) 

const int N=1e5+2;
const int inf=1e9+9;

template <typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}

int s,t,r[N],tot(1),head[N],vis[N],dist[N];
struct Edge{int nxt,to,val,cot;}G[N<<8];
struct Pre{int last,edge;}pre[N];

inline void add(int u,int v,int val,int cot){
    G[++tot].nxt=head[u],G[tot].to=v,G[tot].val=val,G[tot].cot=cot,head[u]=tot;
    G[++tot].nxt=head[v],G[tot].to=u,G[tot].val=0,G[tot].cot=-cot,head[v]=tot;
} 

inline bool Spfa(){
    memset(pre,0,sizeof(pre));
    memset(dist,0x3f,sizeof(dist));
    memset(vis,0,sizeof(vis));
    std::queue<int> q;
    q.push(s),vis[s]=1,dist[s]=0;
    while(!q.empty()){
    	int u=q.front();q.pop();
    	for(int i=head[u];i;i=G[i].nxt){
    	    int v=G[i].to;
    	    if(G[i].val>0&&dist[v]>dist[u]+G[i].cot){
    	        dist[v]=dist[u]+G[i].cot;
                pre[v].last=u,pre[v].edge=i;
                if(!vis[v]){q.push(v),vis[v]=1;} 
    	    } 
    	}vis[u]=0; 
    }return dist[t]!=0x3f3f3f3f;
}

inline ll EK(){
    ll maxflow=0;
    ll cost=0;
    int min_flow;
    while(Spfa()){
        min_flow=inf;
        for(int i=t;i!=s;i=pre[i].last)
           min_flow=min(min_flow,G[pre[i].edge].val);
        for(int i=t;i!=s;i=pre[i].last){
            G[pre[i].edge].val-=min_flow;
            G[pre[i].edge^1].val+=min_flow; 
        }
        maxflow+=min_flow;
        cost+=min_flow*dist[t];
    }return cost; 
}

int main(){
    int n,_n,_p,_m,_f,_s;
    IN(n);s=0,t=n*2+1;
    for(int i=1;i<=n;++i){
        int x;IN(x);
        add(s,id(1,i),x,0),add(id(0,i),t,x,0);
    }
    IN(_p),IN(_m),IN(_f),IN(_n),IN(_s);
    for(int i=1;i<=n;++i){
        if(i+1<=n)add(id(1,i),id(1,i+1),inf,0);
        if(i+_m<=n)add(id(1,i),id(0,i+_m),inf,_f);
        if(i+_n<=n)add(id(1,i),id(0,i+_n),inf,_s);
        add(s,id(0,i),inf,_p);
    }
    printf("%lld\n",EK());
    return 0;
}

本文标题:【题解】 「网络流24题」餐巾计划问题 网络流 luoguP1251

文章作者:Qiuly

发布时间:2019年03月09日 - 00:00

最后更新:2019年03月29日 - 13:52

原始链接:http://qiulyblog.github.io/2019/03/09/[题解]luoguP1251/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。